package day_2022_4_to_7.nowcoder;

import java.util.*;
/**
 * 和为S的连续正数序列
 * @author haomin
 * @date 2022/05/11 11:19
 **/
public class FindContinuousSequence_31f {
    // 方法一：
    public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        //1. 我们可以遍历1到sum，从第一个数开始令total = 这个数
        for (int i = 1; i < sum; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            int total = 0;
            int j = i;
            // 2. 当total < sum 时，total += （i++）
            while (total < sum){
                total += j;
                list.add(j);
                j++;
            }
            // 3. 当total == sum 时，组成 total 的数就是组成sum的数
            if(total == sum){
                System.out.println();
                result.add(list);
            }
            // 4. 当total > sum 时，total 遍历到下一个数
        }
        return result;
    }

    // 方法二：滑动窗口
    // 通项公式为：an=a1+(n-1)*d。首项a1=1，公差d=2。
    // 前n项和公式为：Sn=a1*n+[n*(n-1)*d]/2或Sn=[n*(a1+an)]/2。
    // 注意：以上n均属于正整数
    public static ArrayList<ArrayList<Integer> > FindContinuousSequence2(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // 1. 定义开始数字start，结束数字end
        int start = 1;
        int end = 2;
        // 当start < end 时一直循环
        while (start < end){
            int total = (start + end)*(end-start+1)/2;
            // 2. 当start加到end的和 == sum 时，start到end 之间的数就是组成sum的数；
            if(total == sum){
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = start; i <= end; i++) {
                    list.add(i);
                }
                result.add(list);
                start++;
            }else if(total > sum){
                // 3. 当start加到end的和 < sum 时，说明该序列区间中的数据和小于sum，
                // 应该扩大区间,以包含更多数据 end++；
                start++;
            }else {
                // 4. 当start加到end的和 >sum 时，说明该序列区间中的数据和大于sum，
                // 应该缩小区间,以包含较少数据 start++;
                end++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        FindContinuousSequence(9);
    }
}